Optimal
Implements the Optimal String Alignment algorithm, sometimes called the restricted edit distance variant of the Damerau-Levenshtein distance (Damerau, 1964).
The difference between the two algorithms consists in that the Optimal String Alignment algorithm computes the number of edit operations needed to make the strings equal under the condition that no substring is edited more than once, whereas Damerau-Levenshtein presents no such restriction.
Computes the distance between strings: the minimum number of operations needed to transform one string into the other (insertion, deletion, substitution of a single character, or a transposition of two adjacent characters) while no substring is edited more than once.
The similarity is computed as \(\frac{w_d \lvert X \rvert + w_i \lvert Y \rvert - distance(X, Y)}{2}\).
Note: although the DamerauLevenshtein distance is a metric distance, this is not true for the Optimal String Alignment algorithm. This is because it violates the triangle inequality: \(distance("CA", "AC") + distance("AC", "ABC") < distance("CA", "ABC")\), so it is not a true metric.
References
Damerau, F. J. (1964-03). A technique for computer detection and correction of spelling errors. Communications of the ACM, 7(3), 171-176. https://doi.org/10.1145/363958.363994[sci-hub]
Author
solonovamax
Parameters
The weight of an insertion. Represented as \(w_i\). Must be in the range \([0, 1 \times 10^{10} ]\).
The weight of a deletion. Represented as \(w_d\). Must be in the range \([0, 1 \times 10^{10} ]\).
The weight of a substitution. Represented as \(w_s\). Must be in the range \([0, 1 \times 10^{10} ]\).
The weight of a substitution. Represented as \(w_t\). Must be in the range \([0, 1 \times 10^{10} ]\).
See also
Properties
The weight of a deletion. Represented as \(w_d\).
The weight of an insertion. Represented as \(w_i\).
The weight of a substitution. Represented as \(w_s\).
The weight of a transposition. Represented as \(w_t\).